package kth.csc.inda;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * An undirected graph with a fixed number of vertices implemented using
 * adjacency lists. Space complexity is O(V + E) where V is the number
 * of vertices and E the number of edges.
 * 
 * @author [Name]
 * @version [Date]
 */
public class ListGraph implements UndirectedGraph {
    /** Number of vertices in the graph. */
    private final int numVertices;

    /** Number of edges in the graph. */
    private int numEdges;
    
    private final static int EMPTY = -2;   // no edge
    private final static int NO_COST = -1; // an edge with no cost
    /**
     * All vertices adjacent to v are stored in adjacentVertices[v].
     * No set is allocated if there are no adjacent vertices.
     */
    private final Set<Integer>[] adjacentVertices;

    /**
     * Edge costs are stored in a hash map. The key is an
     * Edge(v, w)-object and the cost is an Integer object.
     */
    private final Map<Edge, Integer> edgeCosts;

    /**
     * Constructs a ListGraph with v vertices and no edges.
     * Time complexity: O(v)
     * 
     * @throws IllegalArgumentException if v < 0
     */
    public ListGraph(int v) { // TODO
        numVertices = v;
        numEdges = 0;
        
        // The array will contain only Set<Integer> instances created
        // in addEdge(). This is sufficient to ensure type safety.
        @SuppressWarnings("unchecked")
        Set<Integer>[] a = new HashSet[numVertices];
        adjacentVertices = a;
        
        edgeCosts = new HashMap<Edge, Integer>();
    }

    /** An undirected edge between v and w. */
    private static class Edge {
        // Invariant: v <= w
        final int v;
        final int w;

        Edge(int v, int w) {
            if (v <= w) {
                this.v = v;
                this.w = w;
            } else {
                this.v = w;
                this.w = v;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Edge))
                return false;
            Edge e = (Edge) o;
            return v == e.v && w == e.w;
        }

        @Override
        public int hashCode() {
            return 31*v + w;
        }

        @Override
        public String toString() {
            return "(" + v + ", " + w + ")";
        }
    }

    /**
     * Returns the number of vertices in this graph.
     * Time complexity: O(1).
     * 
     * @return the number of vertices in this graph
     */
    @Override
    public int numVertices() { 
        return this.numVertices;
    }

    /**
     * Returns the number of edges in this graph.
     * Time complexity: O(1).
     * 
     * @return the number of edges in this graph
     */
    @Override
    public int numEdges() { 
        return this.numEdges;
    }

    /**
     * Returns the degree of vertex v.
     * Time complexity: O(1).
     * 
     * @param  v vertex
     * @return the degree of vertex v
     * @throws IllegalArgumentException if v is out of range
     */
    @Override
    public int degree(int v) throws IllegalArgumentException { 
        return this.adjacentVertices[v]==null ? 0:this.adjacentVertices[v].size();
    }

    /**
     * Returns an iterator of vertices adjacent to v.
     * Time complexity for iterating over all vertices: O(n),
     * where n is the number of adjacent vertices.
     * 
     * @param  v vertex
     * @return an iterator of vertices adjacent to v
     * @throws IllegalArgumentException if v is out of range
     */
    @Override
    public VertexIterator adjacentVertices(int v){
        return new AdjacentVerticesIterator(v);
    }
    private class AdjacentVerticesIterator implements VertexIterator {
    	private Iterator<Integer> it;
		public AdjacentVerticesIterator(int v) {
			try{
				it=adjacentVertices[v].iterator();    
			}
			catch(NullPointerException e){}
		}

		@Override
		public boolean hasNext() {
			return it==null?false : it.hasNext();
		}

		@Override
		public int next() throws NoSuchElementException {
			return it.next();
		}   
    }

    /**
     * Returns true iff v is adjacent to w.
     * Time complexity: O(1).
     * 
     * @param  v vertex
     * @param  w vertex
     * @return true iff v is adjacent to w
     * @throws IllegalArgumentException if v or w are out of range
     */
    @Override
    public boolean areAdjacent(int v, int w) {
        return this.adjacentVertices[v].contains(w);
    }

    /**
     * Returns the edge cost if v is adjacent to w and an edge cost
     * has been assigned, -1 otherwise. Time complexity: O(1).
     * 
     * @param  v vertex
     * @param  w vertex
     * @return true iff v is adjacent to w
     * @throws IllegalArgumentException if v or w are out of range
     */
    @Override
    public int edgeCost(int v, int w) throws IllegalArgumentException {
        return this.edgeCosts.get(new Edge(v,w));
    }

    /**
     * Inserts an undirected edge between vertex positions v and w.
     * (No edge cost is assigned.) Time complexity: O(1).
     * 
     * @param  v    vertex position
     * @param  w    vertex position
     * @throws IllegalArgumentException if v or w are out of range
     */
    @Override
    public void addEdge(int v, int w) {
    	if(!edgeCosts.containsKey(new Edge(v,w))){
    		this.numEdges++;
	    	this.edgeCosts.put(new Edge(v,w), ListGraph.NO_COST);
	    	if(this.adjacentVertices[v]==null)
	    		this.adjacentVertices[v]= new HashSet<Integer>();
	    	this.adjacentVertices[v].add(w);
	    	if(this.adjacentVertices[w]==null)
	    		this.adjacentVertices[w]= new HashSet<Integer>();
	    	this.adjacentVertices[w].add(v);
    	}
    }

    /**
     * Inserts an undirected edge with edge cost c between v and w.
     * Time complexity: O(1).
     * 
     * @param  c edge cost, c >= 0
     * @param  v vertex
     * @param  w vertex
     * @throws IllegalArgumentException if v or w are out of range
     * @throws IllegalArgumentException if c < 0
     */
    @Override
    public void addEdge(int v, int w, int c) {
    	if(!edgeCosts.containsKey(new Edge(v,w))){
    		this.numEdges++;
	    	this.edgeCosts.put(new Edge(v,w), c);
	    	if(this.adjacentVertices[v]==null)
	    		this.adjacentVertices[v]= new HashSet<Integer>();
	    	this.adjacentVertices[v].add(w);
	    	if(this.adjacentVertices[w]==null)
	    		this.adjacentVertices[w]= new HashSet<Integer>();
	    	this.adjacentVertices[w].add(v);
    	}
    }

    /**
     * Removes the edge between v and w.
     * Time complexity: O(1).
     * 
     * @param  v vertex
     * @param  w vertex
     * @throws IllegalArgumentException if v or w are out of range
     */
    @Override
    public void removeEdge(int v, int w) {
    	this.edgeCosts.remove(new Edge(v,w));
    	this.adjacentVertices[v].remove(w);
    	this.adjacentVertices[w].remove(v);
    	this.numEdges--;
    }

    /**
     * Returns a string representation of this graph.
     * 
     * @return a String representation of this graph
     */
    @Override
    public String toString() {
    	VertexIterator vrt;
        StringBuilder sb = new StringBuilder();
        sb.append("Vertices: " + numVertices + ", Edges: {");
        for(int i = 0; i<this.numEdges;i++){
        	vrt = this.adjacentVertices(i);
        	while(vrt.hasNext()){
        		int tempNext = vrt.next();
        		if(i<=tempNext)
        			sb.append("("+i+","+tempNext+"), ");
        	}
        }
        if (numEdges > 0)
            sb.setLength(sb.length() - 2); // Remove trailing ", "
        sb.append("}");
        return sb.toString();
    }
}
